﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
using System.Runtime;
using System.Runtime.InteropServices;
using System.Runtime.Serialization;

namespace Expand.Collections.Generic
{
    public class SingleLinkedList<T> : ICollection<T>, IEnumerable<T>, ICollection, IEnumerable
    {
        public SingleLinkedList(bool isReadOnly = false)
        {
            Count = 0;
            IsReadOnly = isReadOnly;
        }

        private SingleLinkedListNode<T> FirstNode;

        private SingleLinkedListNode<T> LastNode;
        
        /// <summary>
        /// Same as AddLast
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            AddLast(item);
        }

        public void AddFirst(T item)
        {
            if (IsReadOnly) throw new InvalidOperationException("Collection is readonly");

            SingleLinkedListNode<T> tmp = new SingleLinkedListNode<T>(item);
            if (FirstNode != null)
            {
                tmp.Next = FirstNode;
                FirstNode = tmp;
            }
            else
            {
                FirstNode = tmp;
            }
            if (LastNode == null) LastNode = FirstNode;
            Count += 1;
        }

        public void AddLast(T item)
        {
            if (IsReadOnly) throw new InvalidOperationException("Collection is readonly");

            SingleLinkedListNode<T> tmp = new SingleLinkedListNode<T>(item);
            if (LastNode != null)
            {
                LastNode.Next = tmp;
                LastNode = tmp;
            }
            else
            {
                LastNode = tmp;
            }
            if (FirstNode == null) FirstNode = LastNode;
            Count += 1;
        }

        public void Clear()
        {
            if (IsReadOnly) throw new InvalidOperationException("Collection is readonly");

            FirstNode = null;
            LastNode = null;
            Count = 0;
        }

        public bool Contains(T item)
        {
            return SearchItem(item).Item2 != null;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            if ((array.Length - arrayIndex) < Count) throw new ArgumentOutOfRangeException("array", "Array size is not enough for copy");

            SingleLinkedListNode<T> tmp = FirstNode;

            for (int i = 0; i < Count; ++i)
            {
                array[i + arrayIndex] = tmp.Value;
                tmp = tmp.Next;
            }
        }

        public int Count { get; private set; }

        public bool IsReadOnly { get; private set; }

        public bool Remove(T item)
        {
            if (IsReadOnly) throw new InvalidOperationException("Collection is readonly");
            if (IsEmpty) throw new InvalidOperationException("Collection is empty");

            Tuple<SingleLinkedListNode<T>, SingleLinkedListNode<T>> tmp = SearchItem(item);

            if (tmp.Item2 == null) return false;

            if (tmp.Item1 == null)
            {
                RemoveFirst();
                return true;
            }
            else
            {
                tmp.Item1.Next = tmp.Item2.Next;
                Count -= 1;

                if (Count == 1) LastNode = FirstNode;
                if (Count <= 0)
                {
                    FirstNode = null;
                    LastNode = null;
                }
            }

            return true;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="item"></param>
        /// <returns>First value is "previous" node, second value is found node</returns>
        private Tuple<SingleLinkedListNode<T>, SingleLinkedListNode<T>> SearchItem(T item)
        {
            SingleLinkedListNode<T> tmp = FirstNode;
            SingleLinkedListNode<T> previous = null;

            while (tmp != null && !tmp.Value.Equals(item))
            {
                previous = tmp;
                tmp = tmp.Next;
            }

            return new Tuple<SingleLinkedListNode<T>, SingleLinkedListNode<T>>(previous, tmp);
        }

        private SingleLinkedListNode<T> SearchLastItem(T item)
        {
            SingleLinkedListNode<T> tmp = FirstNode;
            SingleLinkedListNode<T> previous = null;
            SingleLinkedListNode<T> found = null;

            while (tmp != null)
            {
                if (tmp.Value.Equals(item)) found = tmp;
                previous = tmp;
                tmp = tmp.Next;
            }

            return found;
        }

        public T First
        {
            get
            {
                if (IsEmpty) throw new InvalidOperationException("Collection is empty");
                return FirstNode.Value;
            }
        }

        public T Last
        {
            get
            {
                if (IsEmpty) throw new InvalidOperationException("Collection is empty");
                return LastNode.Value;
            }
        }

        public bool IsEmpty
        {
            get
            {
                return (Count < 1);
            }
        }
        
        public void RemoveFirst()
        {
            if (IsEmpty) throw new InvalidOperationException("Collection is empty");

            FirstNode = FirstNode.Next;
            Count -= 1;
            if (Count == 1) LastNode = FirstNode;
            if (Count <= 0)
            {
                FirstNode = null;
                LastNode = null;
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public object SyncRoot
        {
            get { return this; }
        }

        public void CopyTo(Array array, int index)
        {
            if ((array.Length - index) < Count) throw new ArgumentOutOfRangeException("array", "Array size is not enough for copy");

            SingleLinkedListNode<T> tmp = FirstNode;

            for (int i = 0; i < Count; ++i)
            {
                array.SetValue(tmp.Value, i + index);
                tmp = tmp.Next;
            }
        }

        public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
        {
            private SingleLinkedListNode<T> _Current;

            private SingleLinkedList<T> _Owner;
            public SingleLinkedList<T> Owner { get { return _Owner; } }

            public Enumerator(SingleLinkedList<T> singleLinkedList)
            {
                _Current = null;
                _Owner = singleLinkedList;
            }

            public T Current
            {
                get
                {
                    if (_Current == null) throw new InvalidOperationException("Current value never moved to next one");
                    else return _Current.Value;
                }
            }

            public void Dispose()
            {
                _Current = null;
                _Owner = null;
            }

            object IEnumerator.Current
            {
                get
                {
                    if (_Current == null) throw new InvalidOperationException("Current value never moved to next one");
                    else return _Current.Value;
                }
            }

            public bool MoveNext()
            {
                if (_Current == null && Owner.FirstNode == null) return false;
                if (_Current == null) _Current = Owner.FirstNode;
                else if (_Current == Owner.LastNode) return false;
                else _Current = _Current.Next;
                return true;
            }

            public void Reset()
            {
                _Current = null;
            }
        }
    }
}
